The present invention relates to apparatus for determining the two-dimensional connectivity of a prescribed binary variable associated with a surface.
Examples of a binary variable of this type are (1) the presence or absence of a fingerprint ridge on the surface of a human finger; (2) the presence or absence of a line drawn or printed on a sheet of paper; and (3) the presence or absence of an electronic circuit lead on the surface of a printed circuit board. In these and other instances it is frequently desirable to determine the "connectivity" of this binary variable between remote points on the surface. That is, it is of importance to know whether the binary variable which is present at two separated points on the surface is also present at a series of contiguous points in between these separated points so that these separated points are, so to speak, "connected".
It is possible and, in fact, known to supply a digital computer with information about the presence or absence of a binary variable at all the points on a two-dimensional grid. Once this information is stored in memory, the computer may determine the connectivity within the two-dimensional binary pattern by means of a suitable software executed algorithm. One type of algorithm follows the so-called "brushfire logic" which involves starting with a grid point at which the binary variable has a value of logical "1", checking the binary variable at its neighboring grid points to determine those which also have a value of "1" (and are, therefore, considered to be "connected" to the initial grid point) and then repeating this procedure with the determined neighboring grid points as a starting point. By this procedure, a string of connected grid points may be followed in progression, much as a brush fire moves progressively along the ground by successively igniting adjacent, flammable parts of the undergrowth.
The brushfire logic algorithm is extremely inefficient, time-consuming and therefore costly in computer time. Frequently, the end result--namely, a connectivity profile of the binary variable--is simply not worth the time and cost of obtaining it.